package com.example.system.class13;

/**
 * @Date 2022/8/2
 * @Author Jonathan
 * @Description 二叉树的最大距离
 */
public class Code04_MaxDistanceBT {
    private static int index = 0;

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1, 2, 3, null, null, 4, 5, null, null, null, null};
        Node bt = createBT(arr);
        System.out.println(maxDistance(bt));
    }


    public static int maxDistance(Node root) {
        return process(root).maxDistance;
    }


    public static Info process(Node x) {
        if (x == null) {
            return new Info(0, 0);
        }
        Info left = process(x.left);
        Info right = process(x.right);
        // 经过当前节点的话就是两边的高度+1
        // 不经过的话 要么就是左边  要么就是右边
        int maxDistance = Math.max(left.height + right.height + 1, Math.max(left.maxDistance, right.maxDistance));
        int height = Math.max(left.height, right.height) + 1;
        return new Info(maxDistance, height);
    }


    static class Info {
        int maxDistance;
        int height;

        public Info(int maxDistance, int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }

    static class Node {
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }
    }


    public static Node createBT(Integer[] arr) {
        if (arr == null || arr.length <= 0) {
            return null;
        }
        return create(arr);
    }

    // 借助全局变量实现
    public static Node create(Integer[] arr) {
        Integer value = arr[index++];
        if (value == null) {
            return null;
        }
        final Node node = new Node(value);
        node.left = create(arr);
        node.right = create(arr);
        return node;
    }
}
